package com.leetcode;

import com.leetcode.common.TreeNode;
import com.leetcode.util.BinaryTreeUtil;

/**
 * 108. 将有序数组转换为二叉搜索树
 * 二分法递归创建左右子树
 * 总是选择中间位置左边的数字作为根节点
 *
 * @author fy
 * @date 2022/4/26 19:24
 */
public class Solution108 {

    public TreeNode sortedArrayToBST(int[] nums) {
        return createBST(nums, 0, nums.length - 1);
    }

    private TreeNode createBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        // 这个判断可以省去, 加上的话可以减少两次递归调用
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        // 总是选择中间位置左边的数字作为根节点
        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = createBST(nums, left, mid - 1);
        root.right = createBST(nums, mid + 1, right);
        return root;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-10, -3, 0, 5, 9};
        TreeNode root = new Solution108().sortedArrayToBST(nums);
        BinaryTreeUtil.printTree(root);
    }

}
